package com.example.doublepointer;

import com.example.structure.ListNode;

/**
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * <p>
 * 进阶：你能尝试使用一趟扫描实现吗？
 * <p>
 * 示例 1：
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * 示例 2：
 * 输入：head = [1], n = 1
 * 输出：[]
 * 示例 3：
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * <p>
 * 思路：
 * 只能遍历一次，那么想到使用双指针来记录位置。
 * 要移去第n个节点，则可建立双指针，分别指向head和dummy节点
 * 指向head的节点先遍历到n，则剩下没遍历的节点数就是：总长度-n
 * 接着双指针同时移动，直到为空。则可以遍历 总长度-n个节点。
 * 此时第二个指针指向的则是被删节点的前一个节点（第n-1个），进行删除即可。
 */
public class RemoveNthNodeFromEndofList {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}
